package book;

import java.util.Arrays;

// 创建背包物品对象，方便后面进行排序
class BagItem implements Comparable<BagItem> {

    double weight, value;

    public BagItem(double w, double v) {
        weight = w; value = v;
    }

    // 比较：单位重量更值钱的物品排在更前面
    public int compareTo(BagItem other) {
        return Double.compare(other.value * this.weight, this.value * other.weight);
    }
}

public class BagSolution {
    // 背包问题：求装入背包最大价值
    double maxValue(int n, double c, double[] w, double[] v) {
        // 将数据转换成对象数组保存
        BagItem[] items = new BagItem[n];
        for (int i = 0; i < n; i++) 
            items[i] = new BagItem(w[i], v[i]);
        Arrays.sort(items); // 实现Comparable接口后可直接排序

        // 维护当前装入背包的总价值
        double totalValue = 0.0;

        // 按单位价值从大到小枚举每件商品
        for (BagItem item : items) {
            if (item.weight <= c) {
                // 物品可以整件装入背包
                totalValue += item.value;
                c -= item.weight;
            } else {
                // 物品只能部分装入背包
                double x = c / item.weight;
                totalValue += item.value * x;
                c = 0;
                break;
            }
        }
        return totalValue;
    }

    public static void main(String[] args) {
        double[] w = {20, 10, 30, 40, 10}, 
            v = {60, 10, 120, 80, 50};
        int n = 5;
        double c = 70;
        double totalValue = new BagSolution().maxValue(n, c, w, v);
        System.out.println("最大价值为: " + totalValue);
    }
}
